'''
https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times
'''

from typing import List


class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        maxi = max(nums)
        maxi_cnt = 0
        for x in nums:
            if x == maxi:
                maxi_cnt += 1
        if maxi_cnt < k: return 0
        r = 0
        cur_cnt = 0
        res = 0
        for l in range(n):
            while r < n and cur_cnt < k:
                if nums[r] == maxi:
                    cur_cnt += 1
                r += 1
            # cur_cnt <= k, r 多走一位
            if cur_cnt == k:
                res += n - r + 1
            else:
                break
            if nums[l] == maxi:
                cur_cnt -= 1
        return res